package other._3;

import java.util.ArrayList;
import java.util.List;

/**
 * [  [],  [1],[2],[1,2],   [3],[1,3],[2,3],[1,2,3]]
 *
 * @author mazouri
 * @create 2021-12-29 17:48
 */
public class Knapsack {
    static List<List<Integer>> res = new ArrayList<>();
    static ArrayList<Integer> ws = new ArrayList<>();
    static ArrayList<Integer> vs = new ArrayList<>();
    static int[] weight = {7, 3, 4, 5};
    static int[] value = {42, 12, 40, 25};
    static int bagSize = 10;

    public static List<List<Integer>> subsets(int[] nums) {
        ws.add(0);
        vs.add(0);
        res.add(new ArrayList<>());

        for (int num : nums) {
            int len = res.size();
            for (int j = 0; j < len; j++) {
                List<Integer> sub = new ArrayList<>(res.get(j));
                sub.add(num);
                res.add(sub);

                ws.add(ws.get(j) + weight[num]);
                vs.add(vs.get(j) + value[num]);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.printf("%-15s", "子集");
        System.out.printf("%-10s", "总重量");
        System.out.printf("%-15s\n", "总价值");
        List<List<Integer>> subsets = subsets(new int[]{0, 1, 2, 3});
        int maxIndex = -1;
        int max = -1;
        for (int i = 1; i < ws.size(); i++) {
            if (vs.get(i) > max && ws.get(i) <= bagSize) maxIndex = i;
            System.out.printf("%-15s", subsets.get(i).toString());
            System.out.printf("%-15d", ws.get(i));
            if (ws.get(i) <= bagSize) System.out.printf("%-20d\n", vs.get(i));
            else System.out.printf("%-20s\n", "不可行");
        }

        System.out.println("总价值最大应选择物品" + subsets.get(maxIndex) + "    总价值为:" + vs.get(maxIndex));
    }
}
